#ifndef HEAD_H
#define HEAD_H
#include<iostream>
#include<string>
using namespace std;

const int len=101;

struct node{
    node*nx;
    char element;
};

class stack{
private:
    node*head;
    node*tail;
    char expression[len];
    int flag=0;
public:
    stack();
    ~stack();
    void init_stack();
    void show();
    void process();
    node* get_pre_tail();
    void nodeprocess();
};

void stack::process(){

    flag=1;

    if(head->nx!=NULL&&flag){
        switch(head->nx->element){
        case'}':
            if(tail->element!='{')
                flag=0;
            else
                nodeprocess();
            break;
        case']':
            if(tail->element!='[')
                flag=0;
            else
                nodeprocess();
            break;
        case')':
            if(tail->element!='(')
                flag=0;
            else
                nodeprocess();
            break;
        default:
            flag=0;
            break;
        }
    }

    if(flag){
        cout<<endl<<"element match perfictly well!";
    }
    else{
        cout<<endl<<"element do not match";
    }
}
node* stack::get_pre_tail(){
    node* p=head;
    while(p->nx!=tail){
        p=p->nx;
    }
    return p;
}
void stack::nodeprocess(){
    node*p;
    node*q;

    p=head;
    head=head->nx;
    delete p;

    p=get_pre_tail();
    q=tail;
    p->nx=NULL;
    tail=p;
    delete q;
}

stack::stack(){
    head=tail=NULL;
    cout<<"input expression:"<<endl;
    string str;
    cin>>str;
    strcpy(expression,str.c_str());
    init_stack();
}

void stack::init_stack(){
    node*p;
    head=tail=new node;
    tail->nx=NULL;
    int i=0;
    while(expression[i]!='\0'){
        switch(expression[i]){
        case'(':case')':case'[':case']':case'{':case'}':
            head->element=expression[i];
            p=head;
            head=new node;
            head->nx=p;
            break;
        }
        i++;
    }
}

void stack::show(){
    node*p=head;
    cout<<endl;
    while(p->nx!=NULL){
        p=p->nx;
        cout<<p->element<<"\t";
    }
}

stack::~stack(){
    node*p;
    while(head!=NULL){
        p=head;
        head=head->nx;
        delete p;
    }
}

#endif // HEAD_H
